package leetcode.templates.trees.segment;

public class SegmentTree {

	public static void main(String[] args) {
		System.out.println("线段树");
	}

	class Node {
		int RANGE;
		int[] arr;
		int[] sum;
		int[] add;
		Integer[] update;

		public Node(int[] array) {
			int n = array.length + 1;
			RANGE = n << 2;
			arr = new int[n];
			for (int i = 1; i < n; i++) {
				arr[i] = array[i - 1];
			}
			sum = new int[RANGE];
			add = new int[RANGE];
			update = new Integer[RANGE];
		}

		private int left(int root) {
			return root << 1;
		}

		private int right(int root) {
			return root << 1 | 1;
		}

		private int mid(int l, int r) {
			return (l + r) >> 1;
		}

		private void sum(int root) {
			sum[root] = sum[root << 1] + sum[root << 1 | 1];
		}

		public void init(int l, int r, int root) {
			if (l == r) {
				sum[root] = arr[l];
			} else {
				int mid = this.mid(l, r);
				this.init(l, mid, this.left(root));
				this.init(mid + 1, r, this.right(root));
				this.sum(root);
			}
		}

		public void add(int L, int R, int A, int l, int r, int root) {
			if (L <= l && r <= R) {
				sum[root] += A * (r - l + 1);
				add[root] += A;
			} else {
				int mid = this.mid(l, r);
				this.push(root, mid - l + 1, r - mid);
				if (L <= mid) {
					this.add(L, R, A, l, mid, this.left(root));
				}
				if (R > mid) {
					this.add(L, R, A, mid + 1, r, this.right(root));
				}
				this.sum(root);
			}
		}

		public void update(int L, int R, int A, int l, int r, int root) {
			if (L <= l && r <= R) {
				update[root] = A;
				sum[root] = A * (r - l + 1);
				add[root] = 0;
			} else {
				int mid = this.mid(l, r);
				this.push(root, mid - l + 1, r - mid);
				if (L <= mid) {
					this.update(L, R, A, l, mid, this.left(root));
				}
				if (R > mid) {
					this.update(L, R, A, mid + 1, r, this.right(root));
				}
				this.sum(root);
			}
		}

		private void push(int root, int ls, int rs) {
			int l = this.left(root), r = this.right(root);
			if (update[root] != null) {
				int a = update[root];
				this.pushUpdate(l, a, ls);
				this.pushUpdate(r, a, rs);
				update[root] = null;
			}
			if (add[root] != 0) {
				int a = add[root];
				this.pushAdd(l, a, ls);
				this.pushAdd(r, a, rs);
				add[root] = 0;
			}
		}

		private void pushUpdate(int root, int A, int size) {
			update[root] = A;
			add[root] = 0;
			sum[root] = A * size;
		}

		private void pushAdd(int root, int A, int size) {
			add[root] += A;
			sum[root] += A * size;
		}

		public long query(int L, int R, int l, int r, int root) {
			if (L <= l && r <= R) {
				return sum[root];
			}
			int mid = this.mid(l, r);
			this.push(root, mid - l + 1, r - mid);
			long ans = 0;
			if (L <= mid) {
				ans += this.query(L, R, l, mid, this.left(root));
			}
			if (R > mid) {
				ans += this.query(L, R, mid + 1, r, this.right(root));
			}
			return ans;
		}

	}
}
